package num1625;

import java.util.HashMap;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/4/15 11:36
 * @Desc :
 */
public class LRUCache2 {
  private int capacity;
  private int count = 0;
  private HashMap<Integer, Node<Integer, Integer>> cache = new HashMap<>();
  private Node<Integer, Integer> head = new Node<>();
  private Node<Integer, Integer> tail = new Node<>();

  public LRUCache2(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
  }

  /**
   * 获取元素，若元素不存在则返回-1；若存在，则将元素移动到链表最前面，并返回元素值。
   * @param key
   * @return
   */
  public int get(int key) {
    Node<Integer, Integer> node = cache.get(key);
    if (node == null) return -1;
    if (head.next != node) moveToHead(node);  // 如果第一个位置，那就移到第一个位置
    return node.value;
  }

  /**
   * 添加元素，在链表最前面、Map里面都添加元素。如果超出了缓存容量，那就删除最末尾的元素。
   * @param key
   * @param value
   */
  public void put(int key, int value) {
    Node<Integer, Integer> node = cache.get(key);
    if (node != null) {
      node.value = value;
      moveToHead(node);
      return;
    }

    // 如果超过了缓存容量，那就删除最尾部的结点
    if (count >= capacity) {
      cache.remove(deleteTail().key);
      count--;
    }
    count++;
    node = new Node<>(key, value);
    // 在缓存、双向链表中插入
    cache.put(key, node);
    insertHead(node);
  }

  /**
   * 将结点移动到链表最前面
   * @param node
   */
  public void moveToHead(Node<Integer, Integer> node) {
    // 给前后两个结点配对
    node.next.prev = node.prev;
    node.prev.next = node.next;
    // 前一个结点指向head，后一个结点指向head的下一个结点
    node.next = head.next;
    node.prev = head;
    //  让head和head的后一个结点，都指向自己
    head.next.prev = node;
    head.next = node;
  }

  /**
   * 在最前面插入一个结点
   * @param node
   */
  public void insertHead(Node<Integer, Integer> node) {
    // 将node前后指向head和head的下一个
    node.next = head.next;
    node.prev = head;
    // 修改head和head下一个结点的指向，指向自己
    head.next.prev = node;
    head.next = node;
  }

  /**
   * 在末尾删除一个结点
   * @return
   */
  public Node<Integer, Integer> deleteTail() {
    Node<Integer, Integer> node = tail.prev;
    tail.prev = tail.prev.prev;
    tail.prev.next = tail;  // 新的前一个结点，让他修改为指向自己
    return node;
  }

  class Node<K, V> {
    private K key;
    private V value;
    private Node<K, V> next;
    private Node<K, V> prev;

    public Node() {
    }

    public Node(K key, V value) {
      this.key = key;
      this.value = value;
    }
  }
}

